The present invention relates to encryption, and in particular to a method and device for providing a controllable and secure way of determining an encryption key for use in an encryption algorithm.
In communication systems, data is often encrypted before transmission to assure privacy and data integrity. The encryption of data takes place in an encryption algorithm. The encryption algorithm manipulates or encodes the transmission data using other data, mathematical operations and/or other means to perform such encryption. For example, the encryption algorithm utilizes a data parameter known as an encryption key, referred to herein by the variable K′c, in its initialization procedure. The encryption key is created in part from a ciphering key or secret key, referred to herein as Kc, where Kc is known to both the receiving device and the transmitting device for encrypting and decrypting the data.
Governments regulate export communication parts and devices that are used in the encryption and transmission of data, including but not limited to, encryption software and hardware. Such export regulations differ among different countries. Specifically, governments regulate the maximum allowable key length of ciphering keys available to the export devices. The users who transmit and receive encrypted data would prefer to use the best possible, that is, the longest possible, ciphering key, to maximize security; however, these users are limited by governmental regulations of the ciphering key.
Assume current technology provides for key lengths of the ciphering key, Kc, to be between 1 and 160 bytes (8 and 1280 bits). Governments typically limit the maximum allowable ciphering key length to, for example, 7 bytes (56 bits). To go beyond this ciphering key length, a manufacturer would have to apply for an export license. Communication devices, e.g., cellular phones, typically utilize the maximum ciphering key length permitted for the particular device under the applicable export regulations. The maximum ciphering key length should be stored in such a way to prevent users from easily manipulating the parameter to ensure compliance with governmental regulations. For example, this parameter could be stored in READ ONLY memory (ROM). However, from a manufacturing point of view, it is desirable to produce communication devices that are able to work in many different countries, thereby avoiding customization and permitting a user to use the same communication device in different geographic locations. The manufacturer would prefer to make a universal product with a standardized method of encryption that complies with the different regulations set by a variety of governments and also provides a high level of data security.
Currently, an encryption key, K′c, together with other public parameters, such as a master clock, is used in the initialization of an encryption algorithm. Encryption key, K′c, utilizes the ciphering key, Kc, and a public random number, designated RAND, in accordance with the following equation:                                           K            c            ′                    ⁡                      [                          0              ⁢                                                           ⁢              …              ⁢                                                           ⁢              15                        ]                          =                  {                                                                                                                                        K                        c                                            ⁡                                              [                                                                              0                            ⁢                                                                                                                   ⁢                            …                            ⁢                                                                                                                   ⁢                            L                                                    -                          1                                                ]                                                              ⋃                                          RAND                      ⁡                                              [                                                  L                          ⁢                                                                                                           ⁢                          …                          ⁢                                                                                                           ⁢                          15                                                ]                                                                              ,                                                                                                  L                    <                    16                                    ,                                                                                                                                                K                      c                                        ⁡                                          [                                              0                        ⁢                                                                                                   ⁢                        …                        ⁢                                                                                                   ⁢                        15                                            ]                                                        ,                                                                              L                  =                  16.                                                                                        (                  EQ          .                                           ⁢          1                )            where L is 1≦L≦min {LAmax, LBmax} in bytes; andwhere RAND [L . . . 15] denotes the bytes L through 15 of RAND.
For exemplary purposes, the maximum usable encryption key length in bytes, Lmax, is assumed to be 16 bytes, although different encryption key lengths could be used.
As disclosed by the above equation, the encryption key, K′c, is created by affixing a random number to the end of the ciphering key, Kc, to complete the entire amount of available bytes for the encryption key length, i.e., 16 bytes in this case. The parameter L represents the smaller ciphering key length allowed between two ciphering key lengths, LAmax and LBmax of first communication device A and second communication device B which are manufactured under different governmental regulations. In other words, the ciphering key length used in computing the encryption key, K′c, is the lesser of the two ciphering key lengths allowed to be used by the first and second communication devices A and B. Both devices can use encrypted communications with the smaller key length, but only one device can use encrypted communication with the larger key length.
One problem with the above equation for generating encryption key, K′c, is that it is difficult to ensure that the hardware implementing the encryption algorithm is not altered by software that overrides the preset values of Lmax. Furthermore, the RAND parameter, being public, can be misused to achieve an effective key length is not restricted at all, i.e., K′c has a maximum number of effective key bits.
An alternative solution is to reduce the space provided for the encryption key, K′c, to L bytes in the memory of the communication device to prevent the software from altering this length. This can be accomplished by “masking out” the entire amount of available bytes minus L bytes of the ciphering key, K′c, and ignoring the RAND. For example, in this case, because the maximum encryption key length is assumed to be 16, 16 minus L bytes would be “masked out,” or in other words, replaced with zeros or some other fixed string. The resulting encryption key, K′c, would then consist of Kc for the first L bytes and zeros or some other fixed string for the next 16−L bytes (128−8L bits).
However, for small byte values of L, at least two undesirable consequences result from this solution. First, during the initialization of the encryption algorithm, the encryption algorithm shuffles the encryption key, K′c, and determines a starting point of the encryption algorithm. To achieve a strong encryption, the shuffling period would need to be increased because of the “non-randomness” of the large fixed string in the 16 minus L bytes, where L is small. As the length of the “random” part of the encryption key decreases, the encryption algorithm would ideally increase the shuffling period, or number of iterations performed, in determining a starting point of the encryption key to compensate for the small length of “random” bits to achieve a better encryption. However, the number of the iterations able to be performed is limited by the strict timing requirements set in transmitting/receiving switching. Thus, this creates a risk of a weak encryption.
Second, an unauthorized person attempting to decrypt the encrypted data or performing a “ciphering attack,” would only need to consider or analyze the first L bytes of the ciphering key, Kc. In other words, the unauthorized person would only need to analyze the possible combinations of data in L bytes rather than the larger maximum usable encryption key length, in this case, 16 bytes, for small values of L. This creates a risk of unauthorized decryption.
In general, a good encryption algorithm receives as its input, one of, for example, 28L possible starting points in a binary system. Where L is 16 bytes, a good encryption algorithm would receive 2128 possible starting points in a binary system. Each of the possible combinations of the 8L K′c bits would define one starting point out of the 28L starting points. An unauthorized person trying to decrypt encrypted data would have to try up to 28L possible combinations to do so. Fewer starting points are available where governmental regulations have restricted the key length. For example, if a government restricts a ciphering key length to a maximum of 5 bytes (40 bits), an encryption algorithm would have a reduced number of starting points, that is 240 starting points. Moreover, if one considers the space, or memory, available for storing all the possible 28L starting points, current technology typically restricts the total available memory to a specific area of the memory for storing the reduced number of starting points and does not use the remaining part of the memory. The remaining positions are constant. Thus, an unauthorized person trying to decrypt encrypted data would only have to analyze 240 starting points and the unauthorized person would know where such starting points where located in memory.